public class demo44 {
    //爬楼梯（简单dp)
    class Solution {
        public int climbStairs(int n) {
            //1.建表
            int[] dp = new int[n+1];
            //2.初始化
            dp[0] = 0;
            dp[1] = 1;
            if(n==1) return dp[1];
            dp[2] = 2;
            if(n==2) return dp[2];
            //3.状态转换方程+填表
            for(int i = 3;i<=n;i++)
                dp[i] = dp[i-2] + dp[i-1];
            //4.返回值
            return dp[n];
        }
    }
}
